The present invention relates to a method and apparatus of accessing items of information. The present invention also relates to a method and apparatus for entropy encoding and decoding symbols.
The field of digital data compression and in particular digital image compression has attracted great interest for some time.
In the field of digital image compression, many different techniques have been utilised. In particular, one popular technique is the JPEG standard, which utilises the Discrete Cosine Transform to transform standard size blocks of an image into corresponding cosine components. In this respect, the higher frequency cosine components are heavily quantised so as to assist in obtaining substantial compression factors. The heavy quantisation is an example of a xe2x80x9clossyxe2x80x9d technique of image compression. The JPEG standard also provides for the subsequent xe2x80x9closslessxe2x80x9d compression of the transformed coefficients.
A call for proposals for the new JPEG-2000 standard was recently issued and a draft standard has been published entitled xe2x80x9cInformation Technologyxe2x80x94JPEG 2000 Image coding Systemxe2x80x94JPEG 2000 Committee Draft version 1.0, Dec. 9, 1999xe2x80x9d. This draft standard proposes that the whole image is firstly discrete wavelet transformed and divided into a number of code blocks of transform coefficients before each code block is entropy encoded. The entropy encoder consists of two parts: a context generator and an arithmetic coder. The arithmetic coder takes as input the bit symbol of a coefficient to be encoded and the context of that bit symbol. The arithmetic coder first codes all the bit symbols of the most significant bit-plane of a code block, then all the bit symbols of the next lower bit-plane of the code block and so on to the least significant bit-plane. Within each bit-plane of a code block, the arithmetic coder codes the bit symbols of the coefficients in a predetermined order. The context of a bit symbol of a coefficient, which bit symbol is to be coded by the arithmetic coder, is based on the xe2x80x98significancexe2x80x99 state of the 8 surrounding coefficients in the code block. When the surrounding coefficient is outside the code block, it can be symmetrically reflected or assumed to be zero. The xe2x80x98significancexe2x80x99 state of a coefficient is a binary-valued variable, "sgr"i[m,n], which is initialised to 0, but transitions to 1 when the coefficient""s first non-zero bit-plane value is encoded. For example, a pixel coefficient having an integer value of seven and thus a binary value of 00111 will have a xe2x80x98significancexe2x80x99 state of zero in bit-planes four and three and a xe2x80x98significancexe2x80x99 state of one in bit-planes two, one and zero. It has been proposed to use a memory table for the look-up and update of the context generation. One proposal is to have a number of identical tables storing identical information on the xe2x80x98significancexe2x80x99 state of the coefficients. In this apparatus, the different locations are simultaneously looked up in respective tables to obtain the xe2x80x98significancexe2x80x99 state of the surrounding coefficients. Thus, all the data is duplicated many times, and the hardware cost may be large. Another proposal is to have one table and look up the table several times to obtain the xe2x80x98significancexe2x80x99 state of all the coefficients in the neighbourhood. This has the advantage of low hardware cost, but this architecture is too slow.
It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements.
According to a first aspect of the invention, there is provided apparatus for accessing items of information in a neighbourhood of a location of a symbol specified by an input address, the apparatus comprising: a plurality of memory banks, wherein each memory bank is capable of storing items of information associated with and corresponding to respective symbols of a sub-set of said symbols, wherein the sub-sets of symbols together comprise a set of symbols, and said items of information of said plurality of memory banks together constitute the whole said items of information associated with and corresponding to respective said symbols of said set of symbols; and an address generator for simultaneously generating a plurality of addresses for respective said plurality of memory banks in response to said input address, wherein said plurality of memory banks output a said plurality of said items of information associated with and corresponding to respective said symbols within said neighbourhood of said symbol corresponding to said input address.
According to a second aspect of the invention, there is provided an entropy encoder for encoding symbols, the entropy encoder comprising: a plurality of memory banks, wherein each memory bank is capable of storing items of information associated with and corresponding to respective symbols of a sub-set of said symbols, wherein the sub-sets of symbols together comprise a set of symbols, and said items of information of said plurality of memory banks together constitute the whole said items of information associated with and corresponding to respective said symbols of said set of symbols; an arithmetic encoder for arithmetically encoding an input symbol utilising a context of said input symbol; an address generator for simultaneously generating a plurality of addresses for respective said plurality of memory banks in response to one input address corresponding to said input symbol, wherein said plurality of memory banks output a said plurality of said items of information associated with and corresponding to respective said symbols within a neighbourhood of said input symbol corresponding to said input address; and a context generator for generating said context of said input symbol utilising said items of information output by said plurality of memory banks.
According to a third aspect of the invention, there is provided an entropy decoder for decoding symbols, the entropy decoder comprising: a plurality of memory banks, wherein each memory bank is capable of storing items of information associated with and corresponding to respective decoded symbols of a sub-set of said decoded symbols, wherein the sub-sets of decoded symbols together comprise a set of decoded symbols, and said items of information of said plurality of memory banks together constitute the whole said items of information associated with and corresponding to respective said decoded symbols of said set of decoded symbols; an arithmetic decoder for arithmetically decoding an input symbol utilising a context of said input symbol; an address generator for simultaneously generating a plurality of addresses for respective said plurality of memory banks in response to one input address corresponding to said input symbol, wherein said plurality of memory banks output a said plurality of said items of information associated with and corresponding to respective said decoded symbols within a neighbourhood of said input symbol corresponding to said input address; and a context generator for generating said context of said input symbol utilising said items of information output by said plurality of memory banks.
According to a fourth aspect of the invention, there is provided a method of accessing items of information in a neighbourhood of a location of a symbol specified by an input address, the method comprising: storing items of information associated with and corresponding to respective symbols of a sub-set of said symbols in each one of a plurality of memory banks, wherein the sub-sets of symbols together comprise a set of symbols, and said items of information of said plurality of memory banks together constitute the whole said items of information associated with and corresponding to respective said symbols of said set of symbols; and simultaneously generating a plurality of addresses for respective said plurality of memory banks in response to said input address, wherein said plurality of memory banks output a said plurality of said items of information associated with and corresponding to respective said symbols within said neighbourhood of said symbol corresponding to said input address.
According to a fifth aspect of the invention, there is provided a method of entropy encoding symbols, the method comprising: storing items of information associated with and corresponding to respective symbols of a sub-set of said symbols in each one of a plurality of memory banks, wherein the sub-sets of symbols together comprise a set of symbols, and said items of information of said plurality of memory banks together constitute the whole said items of information associated with and corresponding to respective said symbols of said set of symbols; arithmetically encoding an input symbol utilising a context of said input symbol; simultaneously generating a plurality of addresses for respective said plurality of memory banks in response to one input address corresponding to said input symbol, wherein said plurality of memory banks output a said plurality of said items of information associated with and corresponding to respective said symbols within a neighbourhood of said input symbol corresponding to said input address; and generating said context of said input symbol utilising said items of information output by said plurality of memory banks.
According to a sixth aspect of the invention, there is provided a method of entropy decoding symbols, the method comprising: storing items of information associated with and corresponding to respective decoded symbols of a sub-set of said decoded symbols in each one of a plurality of memory banks, wherein the sub-sets of decoded symbols together comprise a set of decoded symbols, and said items of information of said plurality of memory banks together constitute the whole said items of information associated with and corresponding to respective said decoded symbols of said set of decoded symbols; arithmetically decoding an input symbol utilising a context of said input symbol; simultaneously generating a plurality of addresses for respective said plurality of memory banks in response to one input address corresponding to said input symbol, wherein said plurality of memory banks output a said plurality of said items of information associated with and corresponding to respective said decoded symbols within a neighbourhood of said input symbol corresponding to said input address; and generating said context of said input symbol utilising said items of information output by said plurality of memory banks.